What We're Building 🎯
-
The Data Structure: A Priority Queue (PQ).
- It's an abstract data type like a list or queue, but with a twist.
- Every item has a "priority" (a key).
- When you "pop," you always get the item with the highest priority.
-
The Operations:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- The Implementation: We'll use a Binary Max-Heap.
-
Why a Heap? It's efficient! A heap gives us:
push: O(log N)pop: O(log N)peek: O(1)
What is a Max-Heap?
A binary tree with two simple rules:
1. Shape Property
It's a complete binary tree. All levels are full, except *maybe* the last, which is filled left-to-right. There are no gaps.
Click a leaf to remove
2. Max-Heap Property
A parent's key is greater than or equal to its children's keys. This guarantees the largest element is always at the root.
Storing the Tree 💾
Because the tree is complete, we can store it perfectly in a simple array.
Index Math (0-based)
For a node at index i:
-
Parent
(i - 1) // 2 -
Left Child
2 * i + 1 -
Right Child
2 * i + 2
Guidance: Memorize these formulas! They are the key to navigating the "tree" inside your array.